# coding:utf-8
# author:fxh

#递归--思维
import time
'''
递归 VS 迭代
递归函数是一种自我调用的函数
递归 时间复杂度：O(n)
空间复杂度：大于跌代
递归调用最大深度：最大为1000左右：
递归超过最大深度报错：RecursionError: maximum recursion depth exceeded in comparison

阶乘
0 ！= 1
N ！= N*(N-1) if N>0
斐波那契
f(0)=0,f(1)=1
f(n)=f(n-1)+f(n-2) n>1

递归思路：
递归终止条件：Base
递归表达式： f(n) = f(n-1)
'''
#阶乘-递归实现
#时间复杂度：O(n)
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

#阶乘-迭代实现
#时间复杂度：O(n)
def factorial1(n):
    result = 1
    for i in range(1,n+1):
        result *=i
    return result

#斐波那契-递归
def fibonacci(n):
    if n>=0 and n <=2:
        return 1
    elif n < 0:
        raise RuntimeError("数字不能小于零")
    return fibonacci(n-1)+fibonacci(n-2)

#斐波那契-迭代
def fibonacci1(n):
    a , b = 0,1
    for i in range(1,n+1):
        a,b = b,a+b
    return a


if __name__ == '__main__':
    assert factorial(2) == 2
    assert factorial(5) == 120

    assert factorial1(5) == 120
    assert factorial1(6) == 720

    assert fibonacci(0) == 1
    assert fibonacci(1) == 1
    assert fibonacci(2) == 1
    assert fibonacci(5) == 5
    assert fibonacci(6) == 8
    assert fibonacci1(40) == 102334155



